package algorthm.systemTraning.mergeSort.biggerTwice;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * @className: BiggerTwice
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/23 14:07
 */
public class BiggerTwice {
    private static Logger logger = LoggerFactory.getLogger(BiggerTwice.class);
    public static int mergeSort(int[] array){
        if(array == null || array.length == 0){
           return -1;
        }
        return process(array , 0 , array.length - 1);
    }
    public static int process(int[] array , int start , int end){
        int cnt = 0 ;
        if(start == end){
            return 0 ;
        }
        int mid = (start + end) >> 1;
        return process(array , start , mid)  + process(array , mid + 1 , end) + merge(array , start , mid , end);
    }
    public static int merge(int[] array , int start , int mid , int end){
        int cnt = 0 ;
        int[] help = new int[end - start + 1];
        int h = 0 ;
        int i = start ;
        int j = mid + 1 ;
        while(i <= mid && j <= end){
//            if(array[i] <= array[j]){
//                help[h++] = array[i++];
//            }else{
//                help[h++] = array[j++];
//            }
            int win = 0 ;
            while(win <= end && (array[win++]<<1) < array[i]){
                cnt++;
            }
            help[h++] = (array[i] <= array[j]? array[i++]:array[j++]);
        }

        while(i <= mid){
            help[h++] = array[i++];
        }
        while(j <= end){
            help[h++] = array[j++];
        }
        for(int p = 0 ; p < help.length ; p++){
            array[start + p] = help[p];
        }
        return cnt ;
    }

    public static void main(String[] args) {
        int[] a = {11 , 243 , 121232 ,11 , 12 ,45 };
        System.out.println(mergeSort(a));
    }
}
